package com.example.leetcode.tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 二叉树层序遍历
 * <p>
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[3],[9,20],[15,7]]
 * *
 * 输入：root = []
 * 输出：[]
 * <p>
 * 思路：广度优先搜索(BFS)
 */
public class LevelOrder {
    public static void main(String[] args) {

        TreeNode treeNode1 = new TreeNode(3);
        TreeNode treeNode2 = new TreeNode(9);
        TreeNode treeNode3 = new TreeNode(20);
        TreeNode treeNode4 = new TreeNode(15);
        TreeNode treeNode5 = new TreeNode(7);

        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode3.left = treeNode4;
        treeNode3.right = treeNode5;

        List<List<Integer>> lists = levelOrder(treeNode1);
        System.out.println(lists);
    }



    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        // 定义一个队列,存放同一层元素
        Deque<TreeNode> deque = new ArrayDeque<>();

        // 添加根节点
        deque.add(root);
        while (!deque.isEmpty()) {
            // 存储同一层元素
            List<Integer> temp = new ArrayList<>();

            // 遍历同一层元素
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = deque.poll();
                temp.add(treeNode.val);

                // 获取下一层元素
                TreeNode left = treeNode.left;
                TreeNode right = treeNode.right;
                if (left != null) {
                    deque.add(left);
                }
                if (right != null) {
                    deque.add(right);
                }
            }

            result.add(temp);
        }
        return result;
    }
}
